import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

public class Solution752 {
    public char turnTable(char tmpC,int mod){
        if(mod==0){
            char newC= (char) (tmpC-1);
            return newC<'0'? '9':newC;
        }
        else{
            char newC= (char) (tmpC+1);
            return newC>'9'? '0':newC;
        }
    }


    public int openLock(String[] deadends, String target) {
        if(target.equals("0000")){ return 0;}
        Set<String> deadSet=new HashSet<>();
        for (String tmpStr:deadends) {
            deadSet.add(tmpStr);
        }
        Queue<String> bpQueue=new LinkedList<>();
        bpQueue.offer("0000"+'0');
        Set<String> seenSet=new HashSet<>();
        seenSet.add("0000");
        while(!bpQueue.isEmpty()){
            String tmpEle=bpQueue.poll();
            int count=Integer.valueOf(tmpEle.substring(4));
            tmpEle=tmpEle.substring(0,4);
            if(target.equals(tmpEle)){
                return count;
            }
            else if(deadSet.contains(tmpEle)){
                continue;
            }
            for (int i = 0; i < 8; i++) {
                int opInd=i/2, opMtd=i%2;
                StringBuilder newEle=new StringBuilder(tmpEle);
                char tmpC=turnTable(newEle.charAt(opInd),opMtd);
                newEle.setCharAt(opInd,tmpC);
                String newStr=newEle.toString();
                if(!seenSet.contains(newStr)) {
                    bpQueue.offer(newStr + (count + 1));
                    seenSet.add(newStr);
                }
            }
        }
        return -1;
    }


}
